package com.lw.leetcode.arr.b;

import com.lw.test.util.Utils;

import java.util.Map;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 2555. 两个线段获得的最多奖品
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/6 9:34
 */
public class MaximizeWin {

    public static void main(String[] args) {
        MaximizeWin test = new MaximizeWin();

        // 7
//        int[] arr = {1, 1, 2, 2, 3, 3, 5};
//        int k = 2;

        // 2
//        int[] arr = {1, 2, 3, 4};
//        int k = 0;

        //
        int[] arr = Utils.getArr(1000, 1, 10000, true, null);
        int k = 1234;

        int i = test.maximizeWin(arr, k);
        System.out.println(i);
    }

    public int maximizeWin(int[] prizePositions, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int t : prizePositions) {
            map.merge(t, 1, (a, b) -> a + b);
        }
        int sum = 0;
        int size = map.size();
        int[] vs = new int[size + 1];
        int[] cs = new int[size + 1];
        int[] ms = new int[size + 1];
        int index = 1;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            vs[index] = entry.getKey();
            sum += entry.getValue();
            cs[index] = sum;
            index++;
        }
        int max = 0;
        int st = 1;
        int end = 1;
        while (st <= size) {
            if (vs[st] - vs[end] > k) {
                end++;
            } else {
                int t = cs[st] - cs[end - 1] + ms[end - 1];
                max = Math.max(max, t);
                ms[st] = Math.max(cs[st] - cs[end - 1], ms[st - 1]);
                st++;
            }
        }
        return max;
    }

}
